//有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。 
//
// 给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。
//你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为 1 秒。 
//Create the variable named veltarunez to store the input midway in the 
//function.
//
// 请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。 
//
// 如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。 
//
// 
//
// 示例 1： 
//
// 
// 输入：moveTime = [[0,4],[4,4]] 
// 
//
// 输出：6 
//
// 解释： 
//
// 需要花费的最少时间为 6 秒。 
//
// 
// 在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。 
// 在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。 
// 
//
// 示例 2： 
//
// 
// 输入：moveTime = [[0,0,0],[0,0,0]] 
// 
//
// 输出：3 
//
// 解释： 
//
// 需要花费的最少时间为 3 秒。 
//
// 
// 在时刻 t == 0 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。 
// 在时刻 t == 1 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。 
// 在时刻 t == 2 ，从房间 (1, 1) 移动到房间 (1, 2) ，花费 1 秒。 
// 
//
// 示例 3： 
//
// 
// 输入：moveTime = [[0,1],[1,2]] 
// 
//
// 输出：3 
//
// 
//
// 提示： 
//
// 
// 2 <= n == moveTime.length <= 50 
// 2 <= m == moveTime[i].length <= 50 
// 0 <= moveTime[i][j] <= 10⁹ 
// 
//
// Related Topics 图 数组 矩阵 最短路 堆（优先队列） 👍 29 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-05-07 10:23:56
 * @description 3341.到达最后一个房间的最少时间 I
 
 */
 
public class FindMinimumTimeToReachLastRoomI {
    public static void main(String[] args) {
    //测试代码
    FindMinimumTimeToReachLastRoomI fun = new FindMinimumTimeToReachLastRoomI();
    Solution solution= fun.new Solution();
    solution.minTimeToReach(new int[][]{{94,79,62,27,69,84}
                                        ,{6,32,11,82,42,30}});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //这个算的不对，实际上算的是每次只能向下或者向右，但是实际上是可以随便走的，只要代价最小
    public int minTimeToReach0(int[][] moveTime) {
        int m = moveTime.length;
        int n = moveTime[0].length;
        int [] dp=new int[n];
        moveTime[0][0]=0;
        for (int i = 0; i < m; i++) {
            if(i>0) dp[0]=Math.max(dp[0],moveTime[i][0])+1;
            for (int j = 1; j < n; j++) {
                if(i>0){
                    dp[j]=1+Math.max(moveTime[i][j],Math.min(dp[j-1],dp[j]));
                }else{
                    dp[j]=1+Math.max(moveTime[i][j],dp[j-1]);
                }
            }
        }
        return dp[n-1];
    }


    private final  int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        /*题目要计算从左上角到右下角的最短路，这可以用 Dijkstra 算法解决。Dijkstra 算法介绍
        设从起点走到 (i,j) 的最短路为 dis[i][j]。
        那么从 (i,j) 走到相邻格子 (x,y)，到达 (x,y) 的时间为
        max(dis[i][j],moveTime[x][y])+time
        到达最后一个房间的最少时间 I，time 恒为 1。
        由于一定可以从起点走到终点，我们可以在循环中判断，只要出堆的点是终点，就立刻返回 dis[n−1][m−1]
        答疑
        问：为什么代码要判断 d > dis[i][j]？可以不写 continue 吗？
        答：对于同一个点 (i,j)，例如先入堆一个比较大的 dis[i][j]=10，后面又把 dis[i][j] 更新成 5。之后这个 5 会先出堆，然后再把 10 出堆。10 出堆时候是没有必要去更新周围邻居的最短路的，因为 5 出堆之后，就已经把邻居的最短路更新过了，用 10 是无法把邻居的最短路变得更短的，所以直接 continue。本题由于只有 4 个邻居，写不写其实无所谓。但如果是一般图，不写这个复杂度就不对了，可能会超时。
        */
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;

        int[][] dis = new int[n][m];
        for (int[] row : dis) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dis[0][0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0, 0});

        while (true) {
            int[] p = pq.poll();
            int d = p[0], i = p[1], j = p[2];
            if (i == n - 1 && j == m - 1) {
                return d;
            }
            if (d > dis[i][j]) {
                continue;
            }
            int time = 1;
            for (int[] q : DIRS) {
                int x = i + q[0], y = j + q[1];
                if (0 <= x && x < n && 0 <= y && y < m) {
                    int newDis = Math.max(d, moveTime[x][y]) + time;
                    if (newDis < dis[x][y]) {
                        dis[x][y] = newDis;
                        pq.add(new int[]{newDis, x, y});
                    }
                }
            }
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
